import java.util.*;
class MyCalendar {
    public List<List<Integer>> list=null;
    public int size=0;
    public MyCalendar() {
        this.list=new ArrayList<>();
        this.size=0;
    }

    public boolean book(int start, int end) {
        List<Integer> tmp=new ArrayList<>();
        tmp.add(start);
        tmp.add(end);
        if(size==0){
            list.add(tmp);
            size++;
        }else{
            for(int i=0;i<size;i++){
                List<Integer> l=list.get(i);
                if(!(tmp.get(1)<=l.get(0)||(tmp.get(0)>=l.get(1)))){
                    return false;
                }
            }
            list.add(tmp);
            size++;
        }
        return true;
    }
}





class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}






















public class project {

    public void recoverTree(TreeNode root) {
        List<TreeNode> list=new ArrayList<>();
        dfs(root,list);
        TreeNode left=null;
        TreeNode right=null;
        for(int i=0;i<list.size()-1;i++){
            if(list.get(i).val>list.get(i+1).val){
                right=list.get(i+1);
                if(left==null){
                    left=list.get(i);
                }
            }
        }
        if(left!=null&&right!=null){
            int tmp=left.val;
            left.val=right.val;
            right.val=tmp;
        }
    }
    public void dfs(TreeNode root,List<TreeNode> list){
        if(root==null){
            return;
        }
        dfs(root.left,list);
        list.add(root);
        dfs(root.right,list);
    }























    public static void main(String[] args) {
        int[][] a=new int[][]{{1,4},{3,2}};
        findPeakGrid(a);
    }



    static int[] arr=new int[2];
    public static int[] findPeakGrid(int[][] mat) {
        int row=mat.length;
        int col=mat[0].length;
        dfs1(mat,0,0,row,col);
        return arr;
    }
    public static void dfs1(int[][] mat,int x,int y,int row,int col){
        if(x<0||y<0||x==row||y==col){
            return;
        }
        int left=-1;
        int right=-1;
        int up=-1;
        int lower=-1;
        if(x!=0){
            up=mat[x-1][y];
        }
        if(x!=row-1){
            lower=mat[x+1][y];
        }
        if(y!=0){
            left=mat[x][y-1];
        }
        if(y!=col-1){
            right=mat[x][y+1];
        }
        int val=mat[x][y];
        int max=Math.max(up,Math.max(lower,Math.max(left,Math.max(val,right))));
        if(max==up){
            dfs1(mat,x-1,y,row,col);
        }else if(max==lower){
            dfs1(mat,x+1,y,row,col);
        }else if(max==left){
            dfs1(mat,x,y-1,row,col);
        }else if(max==right){
            dfs1(mat,x,y+1,row,col);
        }else{
            arr[0]=x;
            arr[1]=y;
            return;
        }
    }






















    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> list=new ArrayList<>();
        PriorityQueue<List<Integer>> queue=new PriorityQueue<>(new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                return (o2.get(0)+ o2.get(1))-(o1.get(0)+o1.get(1));
            }
        });
        for(int i=0;i<Math.max(k,nums1.length);i++){
            for(int j=0;j<Math.max(k,nums2.length);j++){
                List<Integer> tmp=new ArrayList<>();
                if(queue.size()<k){
                    tmp.add(nums1[i]);
                    tmp.add(nums2[j]);
                    queue.offer(tmp);
                }else {
                    int q=queue.peek().get(0)+queue.peek().get(1);
                    if(q>nums1[i]+nums2[j]){
                        queue.poll();
                        tmp.add(nums1[i]);
                        tmp.add(nums2[j]);
                        queue.add(tmp);
                    }
                }
            }
        }
        for(int i=0;i<k&&!queue.isEmpty();i++){
            list.add(queue.poll());
        }
        return list;
    }
}
